Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Description
给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
一个整数N
Output
如题
4
Sample Output
4
HINT
1<=N<=10^7
Solution
直接莫比乌斯反演即可。
然后对于这个式子,我们下界分块一下即可。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #include<bits/stdc++.h> using namespace std; typedef long long s64;
const int ONE = 1e7+5;
int T; int n,m; bool isp[ONE]; int prime[664580],p_num; int miu[ONE],sum_miu[ONE]; s64 Ans;
int get() { int res=1,Q=1; char c; while( (c=getchar())<48 || c>57) if(c=='-')Q=-1; if(Q) res=c-48; while((c=getchar())>=48 && c<=57) res=res*10+c-48; return res*Q; }
void Getmiu(int MaxN) { miu[1] = 1; for(int i=2; i<=MaxN; i++) { if(!isp[i]) isp[i] = 1, prime[++p_num] = i, miu[i] = -1; for(int j=1; j<=p_num, i*prime[j]<=MaxN; j++) { isp[i * prime[j]] = 1; if(i % prime[j] == 0) { miu[i * prime[j]] = 0; break; } miu[i * prime[j]] = -miu[i]; } miu[i] += miu[i-1]; } }
int main() { n=get(); Getmiu(n); for(int d=1; d<=p_num; d++) { if(prime[d] > n) break; int N = n/prime[d]; for(int i=1,j=0; i<=N; i=j+1) { j = min(N, N/(N/i)); Ans += (s64)(N/i) * (N/i) * (miu[j] - miu[i-1]); } }
printf("%lld",Ans); }
|